# -*- coding: utf-8 -*-
"""
Created on Sun Sep 20 16:51:10 2020

@author: Administrator
"""

'''
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
'''

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        '''
        20200920--李运辰
        
        
        p
        0,0,0
        0,0,0
        0,0,0
        
        
        i=0
        j=0,1,2
        
        i=1
        j=0,1,2
        
        i=2
        j=0,1,2
        p
        1 4 5
        2 7 6
        6 8 7
        
        --------------
        1 3 1
        1 5 1
        4 2 1
        
        p
        1 4 5
        2 7 6
        6 8 7
        '''
        m,n= len(grid),len(grid[0])
        p = [[0]*n for _ in range(m)]  
        for i in range(m):
            for j in range(n):
                    if i==0 and j==0:
                        p[i][j]=grid[i][j]
                    elif j==0:
                        p[i][j]=grid[i][j]+p[i-1][j]
                    elif i==0:
                        p[i][j]=grid[i][j]+p[i][j-1]
                    else:
                        p[i][j]=min(p[i-1][j],p[i][j-1])+grid[i][j]

        return p[-1][-1]
        